package com.jn.algorithm.day014.question41;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 江南大学1033190417
 * @date 2022/4/29 11:47
 */
public class Solution {

    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] <= 0) {
                nums[i] = length + 1;
            }
        }

        for (int i = 0; i < length; i++) {
            int num = Math.abs(nums[i]);
            if (num <= length) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return length + 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{3, 4, -1, 1};
        System.out.println(solution.firstMissingPositive(nums));
    }
}
